package leetcode100;

import java.util.Arrays;

// TODO 脑筋急转弯 | 排序+双指针 【-】 合并区间
// TODO https://leetcode.cn/problems/merge-intervals/solution/chi-jing-ran-yi-yan-miao-dong-by-sweetiee/

public class lc100_0056 {

    public int[][] merge(int[][] intervals) {
        // 先按照区间起始位置排序
        Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);
        // 遍历区间
        int[][] res = new int[intervals.length][2];

        // 用于记录 res 中有多少个区间
        int index = -1;
        for (int[] interval: intervals) {
            // 如果结果数组是空的，或者当前区间的起始位置 > res 最后区间的终止位置，
            if (index == -1 || interval[0] > res[index][1]) {
                // 则不合并，直接将当前区间加入结果数组。
                res[++index] = interval;
            } else {
                // 反之将当前区间合并至结果数组的最后区间
                res[index][1] = Math.max(res[index][1], interval[1]);
            }
        }
        // 数组后面会有很多个 [0,0]，要截取一下
        return Arrays.copyOf(res, index + 1);
    }

}